package com.LeeCode;

/**
 * 从根到叶的二进制数之和
 */

public class Code1022 {
    public static void main(String[] args) {
        Integer[] arr = {1, 0, 1, 0, 1, 0, 1};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code1022().sumRootToLeaf(root));
    }

    int ans;

    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode root, int num) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            ans += num + root.val;
        }
        int nextNum = (num + root.val) << 1;
        dfs(root.left, nextNum);
        dfs(root.right, nextNum);
    }
}
